package com.study.dataStructure.sortAlgorithms;

import com.study.dataStructure.util.ArraysUtil;

/**
 * @author tiny
 * @date 2021/10/15 21:52
 * @Description: 排序练习
 */
public class SortExercize {

    public static void main(String[] args) {
        int[] arr = creatRandomArr(10000, 100000);

        SortExercize sort = new SortExercize();
        printArr(arr);
//        sort.bubbleSort(arr);
//        sort.insertionSort(arr);
//        sort.selectionSort(arr);
//        sort.shellSort(arr);
//        sort.quickSort(arr,0, arr.length-1);
//        mergeSort(int[] arr,int left,int right,int[] temp)
//        sort.mergeSort(arr,0,arr.length-1,new int[arr.length]);
        sort.radixSort(arr);
        if(ArraysUtil.isSort(arr)){
            printArr(arr);
            System.out.println("数组是顺序排列的！");
        }else{
            printArr(arr);
            System.out.println("数组排序失败!");
        }
    }

    /**
     * 冒泡排序练习
     * @param arr
     * @return
     */
    private int[] bubbleSort(int[] arr){
        if(arr==null || arr.length<=1) return arr;
        //不断地从前往后把数组中最大的一个数往数组末尾挪； 第一次是最末尾，第二次是倒数第二位。。。
        for (int i = 0; i < arr.length-1; i++) {
            boolean swapFlag = false;
            for (int x = 0; x < (arr.length-1-i); x++) {
                if( arr[x]>arr[x+1] ){
                    swap(arr, x, x+1);
                    swapFlag = true;
                }
            }
            if( !swapFlag ) break; //如果一轮比较下来自始自终都没有发生过一次交换位置，则说明数组已经是有序的了
        }
        return arr;
    }

    /**
     * 插入排序练习
     * 思路：
     *  把数组分为两部分：已排序和未排序的；首先，第0索引的元素为已排序，第1到最后为未排序；
     *  不断地用未排序数组第0索引位置的元素依次从与排序末尾到首端去“冒泡”
     * @return
     */
    private int[] insertionSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            for(int y = i; y>0; y--){
                if(arr[y]<arr[y-1]){
                    swap(arr,y,y-1);
                }else
                    break; //注意是直接break，而不是continue!(因为前面已经是排好序的了)
            }
        }
        return arr;
    }

    /**
     * 选择排序
     * 寻找序列中的最小值，用当前位置的值进行交换
     * @param arr
     * @return
     */
    private int[] selectionSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;
            for(int y=i+1; y<arr.length;y++){
                if(arr[y]<arr[minIndex]){
                    minIndex = y;
                }
            }
            swap(arr,i,minIndex);
        }
        return arr;
    }

    /**
     * 希尔排序练习
     * 希尔排序是插入排序的一种，是针对直接插入排序算法的改进,又称缩小增量排序
     * 它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而变小，直到只比较相邻元素的最后一趟排序为止
     * 最内层循环其实就是插入排序
     * @param nums
     */
    private  void shellSort(int[] nums) {
        for(int gap = nums.length/2; gap>0; gap = gap/2){
            for(int j=gap; j<nums.length; j++){
                //插入排序
                for(int i = j; i >= gap; i-=gap){
                    if(nums[i]>nums[i-gap])
                        swap(nums,i,i-gap);
                }
            }
        }
    }

    /**
     * 快速排序
     * @param arr
     * @param low
     * @param high
     */
    /*private static void quickSort(int[] arr, int low, int high) {

        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getIndex(arr, low, high);

            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            //quickSort(arr, 0, index - 1); 之前的版本，这种姿势有很大的性能问题，谢谢大家的建议
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }

    }
    private static int getIndex(int[] arr, int low, int high) {
        // 基准数据
        int tmp = arr[low];
        while (low < high) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            // 如果队尾元素小于tmp了,需要将其赋值给low
            arr[low] = arr[high];
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            arr[high] = arr[low];

        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
        arr[low] = tmp;
        return low; // 返回tmp的正确位置
    }*/

    /**
     * 换一种方式的快排实现,以数组首位为基准位
     */
    public void quickSort(int[] arr,int left,int right){
       int l, r, pivot, temp;
       l = left;
       r = right;
       pivot = arr[left];

        //每一轮交换数组首端的pivot值,都需要保证目标交换值小于原pivot值; 所以需要先由右往左,由右往左,右哨兵停下的位置一定是小于首端pivot的
        // 由于左右哨兵一旦相遇就会停住,不管是否达成大小比较条件,故一定要让右哨兵先行,等左哨兵来跟右哨兵相遇
        //如果是左哨兵是等右哨兵来相遇,左哨兵先行只会在大于pivot的地方停止,右哨兵到此,虽然依旧是大于pivot,但因为已与左哨兵相遇,故会停止;
       while (l<r){
           //右哨兵先行
          while (l<r && arr[r]>=pivot){ //要带上等于号,否则遇上与基准位相等的将陷入死循环
              r--;
          }
          while (l<r && arr[l]<=pivot){ //要带上等于号,否则遇上与基准位相等的将陷入死循环
              l++;
          }
           if(l<r){
               temp = arr[l];
               arr[l] = arr[r];
               arr[r] = temp;
           }
       }
       //一轮交换完,pivot基准位换位置
        if(left<r && pivot > arr[r]){
            arr[left] = arr[r];
            arr[r] = pivot;
        }

        //递归调用前一轮左右哨兵重合点两边的数组
        if(left<r-1){
            quickSort(arr,left,r-1);
        }
        if(right>r+1){
            quickSort(arr,r+1,right);
        }
    }

    /**
     * 归并排序
     * 运用了递归 和 分治的思想
     * 递归，不停地对数组按中间点进行分割，直到分割成以单个元素为数组的最小构成单元
     * 分治，分割完成后，不停的进行排序合并，直到最后全部合并成一个总体是顺序排列的数组
     */
    public void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left<right){ //只有数组不止一个元素，才可以进行再分割
            int mid = (left+right)/2;
            //递归分割左边数组
            mergeSort(arr,left,mid,temp);
            //递归分割右边数组
            mergeSort(arr,mid+1,right,temp);
            //递归分割完后依次合并
            mergeArr(arr,left,mid,right,temp);

        }
    }

    private void mergeArr(int[] arr, int left, int mid, int right, int[] temp) {
        //左半数组的哨兵起始位置
        int l_pos = left;
        //右半数组的哨兵起始位置
        int r_pos = mid+1;
        //临时数组的哨兵位置
        int pos = l_pos;

        while (l_pos<=mid && r_pos<=right){ //只有左右两数组的哨兵都还未检查完成才需继续
            if(arr[l_pos]<=arr[r_pos]){
                temp[pos++] = arr[l_pos++];
            }else{
                temp[pos++] = arr[r_pos++];
            }
        }

        //若哨兵比较完毕后，左或右依旧有未放入临时数组的，则依顺序全部放入临时数组
        while (l_pos <= mid){
            temp[pos++] = arr[l_pos++];
        }
        while(r_pos <= right){
            temp[pos++] = arr[r_pos++];
        }

        //将临时数组中排号序的按依次复制到原数组中的对应范围
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }

    }

    public void radixSort(int[] nums){
        //首先获取数组中最大位数，来决定一会分配到桶有多少轮
        int counts = getMaxCounts(nums);
        for (int i = 0; i < counts; i++) {
            //每一轮准备一个桶用于分配与合并成一个新的序列，供下一轮比较更高一位的数进行排序
            int[][] bucket = new int[10][0];
            for (int x = 0; x < nums.length; x++) {
                //第一轮比较个位数
                int flagNum = (nums[x] / (int)Math.pow(10,i) ) % 10;

                bucket[flagNum] = resizeArr(bucket[flagNum], nums[x]);
            }
            //每一轮在桶中分配完，就合并成新的序列供下一轮比较
            nums = mergeRadix(bucket,nums);
        }
    }

    private int[] mergeRadix(int[][] bucket,int[] nums) {
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            for (int x = 0; x < bucket[i].length; x++) {
                nums[index++] = bucket[i][x];
            }
        }
        return nums;
    }

    private int[]  resizeArr(int[] link, int num) {
        int[] newLink = new int[link.length + 1];
        for (int i = 0; i < link.length; i++) {
            newLink[i] = link[i];
        }
        newLink[link.length] = num;
        return newLink;
    }

    private int getMaxCounts(int[] nums) {
        int maxNum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]>maxNum){
                maxNum = nums[i];
            }
        }
        return String.valueOf(maxNum).length();
    }


    private void swap(int[] arr, int x, int y){
        if( (x>arr.length-1 || x<0) || (y>arr.length-1 || y<0) ){
            throw new RuntimeException();
        }
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    /**
     * 生成一个指定长度，元素数值范围在[0,scope)范围内的随机数组
     * @param length
     * @param scope
     * @return
     */
    private static int[] creatRandomArr(int length,int scope){
        return ArraysUtil.createRandomArr(length, scope);
    }

    private static void printArr(int[] arr){
        StringBuilder sb = new StringBuilder("[");
        for (Object o : arr) {
            sb.append(o);
            sb.append(",");
        }
        String arrStr = (sb.substring(0, sb.length() - 1) ) + "]";
        System.out.println(arrStr);
    }
}
